
public class BinaryHeap {

	private Item[] heap;
	private int lastIndex;
	
	private static final int defaultHeapSize = 7;
	
	public BinaryHeap(){
		this(defaultHeapSize);
	}
	public BinaryHeap(int size){
		heap = new Item[defaultHeapSize];
		lastIndex = -1;
	}
	
	public int size(){
		return lastIndex+1;
	}
	public boolean isEmpty(){
		return lastIndex==-1;
	}
	public double minimumKey(){
		return heap[0].key;
	}
	
	public boolean decreaseKey(Tracker t, double newKey){
		if(newKey < heap[t.index].key){
			heap[t.index].key = newKey;
			while(heap[t.index].key < heap[t.getParentIndex()].key)
				heap[t.index].swap(heap[t.getParentIndex()]);
			return true;
		}
		else 
			return false;
	}
	
	public Object extractMinData(){
		return ((Item)extractMin()).data;
	}
	
	public Object extractMin(){
		if(lastIndex < 0)
			return null;
		Item min = new Item(heap[0].key, heap[0].data);
		
		lastIndex--;
		if(lastIndex>=0){
			heap[0].swap(heap[lastIndex+1]);
			heap[lastIndex+1] = null;
			minHeapify(heap[0].itemTracker);
		}
		
		return min;
	}
	
	public Tracker insert(double key, Object data){
		if(size()>=heap.length)
			growHeap();
		lastIndex++;
		Tracker t = makeAndInsertItemAtIndex(key, data, lastIndex);
		while(heap[t.index].key < heap[t.getParentIndex()].key)
			heap[t.index].swap(heap[t.getParentIndex()]);
		
		return t;
	}
	
	public String toString(){
		String result = "";
		int spaces = 0;
		int nextSpaceIncrease = 1;
		for(int i=0; i<=lastIndex; i++){
			if(i==nextSpaceIncrease){
				spaces++;
				nextSpaceIncrease = (nextSpaceIncrease << 1) + 1;
			}
			for(int j=0; j<spaces; j++)
				result += " ";
			result += heap[i].key + " " + heap[i].data +"\n";
		}
		return result;
	}
	
	
	
	private void minHeapify(Tracker t){
		
		int l = t.getLeftChildIndex();
		int r = t.getRightChildIndex();
		int i = t.index;
		int largest = i;
		if(l <= lastIndex){
			if(heap[l].key < heap[i].key)
				largest = l;
			else
				largest = i;
			
				//inside other block to prevent an otherwise useless if statement
			if(r <= lastIndex)
				if(heap[r].key < heap[largest].key)
					largest = r;
		}
		if(largest != i){
			heap[i].swap(heap[largest]);
			minHeapify(heap[largest].itemTracker);
		}
		
	}
	
	//Makes heap become size 2L+1
	private void growHeap(){
		Item[] newHeap = new Item[(heap.length << 1) + 1];
		for(int i=0; i<heap.length; i++)
			newHeap[i] = heap[i];
		heap = newHeap;
	}
	
	private Tracker makeAndInsertItemAtIndex(double _key, Object _data, int _index){
		Item i = new Item(_key, _data);
		return insertItemAtIndex(i, _index);
	}
	
	private Tracker insertItemAtIndex(Item _item, int _index){
		Tracker t = new Tracker(_index);
		_item.itemTracker = t;
		heap[_index] = _item;
		return t;
	}
	
	
	private class Item {
		private double key;
		private Object data;
		private Tracker itemTracker;
		
		private Item(double _key, Object _data){
			key = _key;
			data = _data;
		}
		
		private Item(Item i){
			key = i.key;
			data = i.data;
			itemTracker = i.itemTracker;
		}
		
		private void swap(Item i){
			int tempIndex = itemTracker.getIndex();
			Item temp = new Item(i);
			itemTracker.index = i.itemTracker.getIndex();
			temp.itemTracker.index = tempIndex;
			heap[itemTracker.getIndex()] = this;
			heap[temp.itemTracker.getIndex()] = temp;
		}
	}
	
	public class Tracker {
		private int index;
		
		public boolean decreaseKey(double newKey){
			if(newKey < heap[this.index].key){
				heap[this.index].key = newKey;
				while(heap[this.index].key < heap[this.getParentIndex()].key)
					heap[this.index].swap(heap[this.getParentIndex()]);
				return true;
			}
			else 
				return false;
		}
		
		private Tracker(int i){
			index = i;
		}
		private int getIndex(){
			return index;
		}
		private void setIndex(int i){
			index = i;
		}
		public Item getItem(){
			return heap[index];
		}
		public Object getData(){
			return heap[index].data;
		}
		public double getKey(){
			return heap[index].key;
		}
		private int getParentIndex(){
			if(index==0)
				return 0;
			return (index -1) >> 1;
		}
		private int getLeftChildIndex(){
			return  ((index + 1) << 1) - 1;
		}
		private int getRightChildIndex(){
			return (index + 1) << 1;
		}
	}
	
	public static void main(String[] args) {
		BinaryHeap bh = new BinaryHeap();
		for(int i =0; i< 25; i++){
			bh.insert(Math.random(), new Integer(i));
		}
		System.out.println(bh + "\n\n REMOVING");

		for(int i =0; i< 15; i++){
			bh.extractMin();
			
			System.out.println("\n\n"+bh );
		}
		
	}

}
